import java.util.Stack;

public class lowestCommonAncestor {

    public static class TreeNode {
        int val;
        TreeNode right;
        TreeNode left;
        TreeNode(int val) {
            this.val = val;
        }
    }

        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

            if (root == null || root == p || root == q) return root;


            Stack<TreeNode> stackP = new Stack<>();
            Stack<TreeNode> stackQ = new Stack<>();


            getPath(root, p, stackP);
            getPath(root, q, stackQ);

            int sizeP = stackP.size();
            int sizeQ = stackQ.size();
            int sz = sizeP - sizeQ;

            //使长路劲先左sz个节点
            if (sz < 0) {
                sz = -sz;
                while (sz != 0) {
                    stackQ.pop();
                    sz--;
                }
            } else {
                while (sz != 0) {
                    stackP.pop();
                    sz--;
                }
            }

            while (!stackQ.empty() && !stackP.empty()) {
                if (stackP.peek() == stackQ.peek()) {
                    return stackP.peek();
                } else {
                    stackP.pop();
                    stackQ.pop();
                }
            }
            return null;
        }

        private boolean getPath(TreeNode root, TreeNode node, Stack stack) {

            if (root == null || node == null) return false;

            stack.push(root);

            if (root == node) return true;
            //是否在左边
            boolean flag1 = getPath(root.left, node, stack);
            if (flag1) {
                return true;
            }
            //是否在右边
            boolean flag2 = getPath(root.right, node, stack);
            if (flag2) {
                return true;
            }
            //不在左，也不在右，弹出
            stack.pop();
            //返回
            return false;
        }
}
